2020 Kakao Internship

Press the Keypad (Lv. 1)
https://school.programmers.co.kr/learn/courses/30/lessons/67256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string type(int num, int& left, int& right, string hand){
if(num==1 || num==4 || num==7){
left=num;
return "L";
} else if(num==3 || num==6 || num==9){
right=num;
return "R";
} else {
if(num==0) num=11;
int tmp_n=num-1, tmp_l=left-1, tmp_r=right-1;
int ldist, rdist;
ldist=abs(tmp_n/3-tmp_l/3)+abs(tmp_n%3-tmp_l%3);
rdist=abs(tmp_n/3-tmp_r/3)+abs(tmp_n%3-tmp_r%3);
if(ldist==rdist) {
if(hand[0]=='l') left=num;
else right=num;
return string(1, toupper(hand[0]));
}
if(ldist>rdist){
right=num;
return "R";
} else{
left=num;
return "L";
}
}
}
string solution(vector<int> numbers, string hand){
string answer="";
int left=10, right=12;
for(int num: numbers){
answer+=type(num, left, right, hand);
}
return answer;
}
int main(void){
vector<int> numbers1={1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5};
vector<int> numbers2={7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2};
vector<int> numbers3={1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
string hand1="right";
string hand2="left";
string hand3="right";
string result1=solution(numbers1, hand1);
string result2=solution(numbers2, hand2);
string result3=solution(numbers3, hand3);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
cout<<"result3: "<<result3<<endl;
return 0;
}
Maximize expression (Lv. 2)
https://school.programmers.co.kr/learn/courses/30/lessons/67257
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
bool compare(int i, int j) {return j<i;}
// sol_op
// +: 0, -: 1, *: 2
void ret_solve(vector<int>& num, vector<int>& op, int sol_op){
vector<int> remove;
for(int i=0; i<op.size(); ++i){
if(op[i]==sol_op){
remove.push_back(i);
switch(sol_op){
case 0:
num[i+1]=num[i]+num[i+1];
break;
case 1:
num[i+1]=num[i]-num[i+1];
break;
case 2:
num[i+1]=num[i]*num[i+1];
break;
}
}
}
sort(remove.begin(), remove.end(), compare);
for(int rm: remove){
num.erase(num.begin()+rm); op.erase(op.begin()+rm);
}
}
ll solution(string expression){
ll answer=0;
vector<bool> op_bool(3, 0);
vector<int> num, op, op_ord;
string str;
for(int i=0; i<expression.length(); ++i){
if(expression[i]=='+'){
if(!op_bool[0])op_bool[0]=1;
op.push_back(0);
} else if(expression[i]=='-'){
if(!op_bool[1])op_bool[1]=1;
op.push_back(1);
} else if(expression[i]=='*'){
if(!op_bool[2])op_bool[2]=1;
op.push_back(2);
}
if(expression[i]>='0' && expression[i]<='9'){
str+=string(1, expression[i]);
} else {
num.push_back(stoi(str));
str.clear();
}
if(i==expression.length()-1){
num.push_back(stoi(str));
str.clear();
}
}
for(int i=0; i<op_bool.size(); ++i){
if(op_bool[i]) op_ord.push_back(i);
}
vector<int> tmp_num, tmp_op;
do{
tmp_num=num; tmp_op=op;
for(int oper: op_ord){
ret_solve(tmp_num, tmp_op, oper);
}
assert(tmp_num.size()==1);
answer=answer<abs(tmp_num[0])? abs(tmp_num[0]): answer;
}while(next_permutation(op_ord.begin(), op_ord.end()));
return answer;
}
int main(void){
string expression1="100-200*300-500+20";
string expression2="50*6-3*2";
ll result1=solution(expression1);
ll result2=solution(expression2);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
return 0;
}
Jewerly Shopping (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/67258
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cassert>
using namespace std;
bool chk(int start, int interv, vector<int> igems, int gem_kind){
vector<bool> used(gem_kind, 0);
for(int i=start; i<=start+interv; ++i){
used[igems[i]]=1;
}
for(bool u: used){
if(!u) return false;
}
return true;
}
vector<int> solution(vector<string> gems){
vector<int> answer;
map<string, int> sti;
vector<int> igems;
int lab=0;
for(string gem: gems){
if(sti.find(gem)==sti.end()) sti[gem]=lab++;
igems.push_back(sti[gem]);
}
assert(gems.size()==igems.size());
int interv=lab-1;
for(int i=interv; i<igems.size(); ++i){
for(int j=0; i+j<igems.size(); ++j){
if(chk(j, i, igems, lab)){
answer.push_back(j+1);
answer.push_back(j+i+1);
return answer;
}
}
}
return answer;
}
void print_vec(vector<int> result){
cout<<"["<<result[0]<<", "<<result[1]<<"]"<<endl;
}
int main(void){
vector<string> gems1={"DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"};
vector<string> gems2={"AA", "AB", "AC", "AA", "AC"};
vector<string> gems3={"XYZ", "XYZ", "XYZ"};
vector<string> gems4={"ZZZ", "YYY", "NNNN", "YYY", "BBB"};
vector<int> result1=solution(gems1);
vector<int> result2=solution(gems2);
vector<int> result3=solution(gems3);
vector<int> result4=solution(gems4);
print_vec(result1); print_vec(result2);
print_vec(result3); print_vec(result4);
return 0;
}
Build racing road (Lv. 3)
https://school.programmers.co.kr/learn/courses/30/lessons/67259
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#define INTMAX 2147483647
using namespace std;
int cost[26][26];
const int dx[]={0, 0, -1, 1};
const int dy[]={-1, 1, 0, 0};
struct point{
int x=0, y=0, cost=0;
bool verti=false;
point(){}
point(int _x, int _y, int _cost, bool _verti): x(_x), y(_y), cost(_cost), verti(_verti) {}
};
void recru(vector<vector<int>>& board, point p, const int N){
if(p.x>=0 && p.x<=N && p.y>=0 && p.y<=N && !board[p.y][p.x]){
if(cost[p.y][p.x]>=p.cost){
cost[p.y][p.x]=p.cost;
for(int i=0; i<4; ++i){
int xx=p.x+dx[i], yy=p.y+dy[i], cc=p.cost;
bool verti;
if((xx==p.x && p.verti) || (yy==p.y && !p.verti)) cc+=100;
else cc+=600;
if(xx==p.x) verti=true;
else verti=false;
point pp(xx, yy, cc, verti);
recru(board, pp, N);
}
}
return;
}
return;
}
int solution(vector<vector<int>> board){
const int N=board.size()-1;
for(int i=0; i<26; ++i) for(int j=0; j<26; ++j) cost[i][j]=INTMAX;
cost[0][0]=0;
recru(board, point(1, 0, 100, false), N);
recru(board, point(0, 1, 100, true), N);
return cost[N][N];
}
int main(void){
typedef vector<vector<int>> vector2;
vector2 board1={
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
vector2 board2={
{0, 0, 0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0, 1},
{0, 0, 1, 0, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 0, 0, 0, 0}
};
vector2 board3={
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 1, 0, 1},
{1, 0, 0, 0}
};
vector2 board4={
{0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 0},
{0, 0, 1, 0, 0, 0},
{1, 0, 0, 1, 0, 1},
{0, 1, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0}
};
int result1, result2, result3, result4;
result1=solution(board1);
result2=solution(board2);
result3=solution(board3);
result4=solution(board4);
cout<<"result1: "<<result1<<endl;
cout<<"result2: "<<result2<<endl;
cout<<"result3: "<<result3<<endl;
cout<<"result4: "<<result4<<endl;
return 0;
}
Traveling cave (Lv. 4)
https://school.programmers.co.kr/learn/courses/30/lessons/67260
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
bool is_near(vector<vector<int>> path, int n1, int n2){
for(int i=0; i<path.size(); ++i){
if((path[i][0]==n1 && path[i][1]==n2) || (path[i][1]==n1 && path[i][0]==n2)){
return true;
}
}
return false;
}
bool reach(vector<vector<int>> path, vector<int> forbid, const vector<int> layer, int obj){
int val=obj;
for(int i=layer[obj]-1; i>0; --i){
vector<int> layer_val;
for(int j=0; j<layer.size(); ++j) if(layer[j]==i) layer_val.push_back(j);
for(int j=0; j<layer_val.size(); ++j){
if(is_near(path, val, layer_val[j])){
if(find(forbid.begin(), forbid.end(), layer_val[j])!=forbid.end()){
return false;
}
val=layer_val[j];
continue;
}
}
}
return true;
}
void fill_layer(const vector<vector<int>>& path, vector<int>& layer, int num, int pnum){
layer[num]=layer[pnum]+1;
vector<int> near;
for(int i=0; i<path.size(); ++i){
if(path[i][0]==num) near.push_back(path[i][1]);
if(path[i][1]==num) near.push_back(path[i][0]);
}
for(int near_val: near){
if(layer[near_val]) continue;
fill_layer(path, layer, near_val, num);
}
}
bool solution(int n, vector<vector<int>> path, vector<vector<int>> order){
bool answer=true;
vector<int> forbid, obj, layer(n, 0);
for(int i=0; i<order.size(); ++i){
obj.push_back(order[i][0]);
forbid.push_back(order[i][1]);
}
fill_layer(path, layer, 0, 1);
sort(obj.begin(), obj.end());
do{
int state=0;
vector<int> forbid_tmp=forbid;
for(int i=0; i<obj.size(); ++i){
if(reach(path, forbid_tmp, layer, obj[i])){
//forbid remove
for(int j=0; j<order.size(); ++j) if(order[j][0]==obj[i]){
forbid_tmp.erase(remove(forbid_tmp.begin(), forbid_tmp.end(), order[j][1]), forbid_tmp.end());
state++;
break;
}
}
else break;
}
if(state==obj.size()){
return true;
}
}while(next_permutation(obj.begin(), obj.end()));
return false;
}
int main(void){
typedef vector<vector<int>> vector2;
int n1=9, n2=9, n3=9;
vector2 path1={
{0, 1}, {0, 3}, {0, 7}, {8, 1}, {3, 6}, {1, 2}, {4, 7}, {7, 5}
};
vector2 path2={
{8, 1}, {0, 1}, {1, 2}, {0, 7}, {4, 7}, {0, 3}, {7, 5}, {3, 6}
};
vector2 path3={
{0, 1}, {0, 3}, {0, 7}, {8, 1}, {3, 6}, {1, 2}, {4, 7}, {7, 5}
};
vector2 order1={{8, 5}, {6, 7}, {4, 1}};
vector2 order2={{4, 1}, {5, 2}};
vector2 order3={{4, 1}, {8, 7}, {6, 5}};
cout<<"result1: "<<solution(n1, path1, order1)<<endl;
cout<<"result2: "<<solution(n2, path2, order2)<<endl;
cout<<"result3: "<<solution(n3, path3, order3)<<endl;
return 0;
}